home *** CD-ROM | disk | FTP | other *** search
/ Hot Super Models / Hot Super Models.iso / unix / x11 / xv200.tar / xv-2.00 / xvgifwr.c < prev    next >
C/C++ Source or Header  |  1992-01-02  |  15KB  |  594 lines
  1. /*
  2.  * xvgifwr.c  -  handles writing of GIF files.  based on flgife.c and
  3.  *               flgifc.c from the FBM Library, by Michael Maudlin
  4.  *
  5.  * Contains: 
  6.  *   WriteGIF(fp, pic, w, h, rmap, gmap, bmap, numcols, colorstyle)
  7.  *
  8.  * Note: slightly brain-damaged, in that it'll only write non-interlaced 
  9.  *       GIF files (in the interests of speed, or something)
  10.  *
  11.  */
  12.  
  13.  
  14.  
  15. /*****************************************************************
  16.  * Portions of this code Copyright (C) 1989 by Michael Mauldin.
  17.  * Permission is granted to use this file in whole or in part provided
  18.  * that you do not sell it for profit and that this copyright notice
  19.  * and the names of all authors are retained unchanged.
  20.  *
  21.  * Authors:  Michael Mauldin (mlm@cs.cmu.edu)
  22.  *           David Rowley (mgardi@watdcsu.waterloo.edu)
  23.  *
  24.  * Based on: compress.c - File compression ala IEEE Computer, June 1984.
  25.  *
  26.  *    Spencer W. Thomas       (decvax!harpo!utah-cs!utah-gr!thomas)
  27.  *    Jim McKie               (decvax!mcvax!jim)
  28.  *    Steve Davies            (decvax!vax135!petsd!peora!srd)
  29.  *    Ken Turkowski           (decvax!decwrl!turtlevax!ken)
  30.  *    James A. Woods          (decvax!ihnp4!ames!jaw)
  31.  *    Joe Orost               (decvax!vax135!petsd!joe)
  32.  *****************************************************************/
  33.  
  34. /*
  35.  * Copyright 1989, 1990, 1991, 1992 by John Bradley and
  36.  *                       The University of Pennsylvania
  37.  *
  38.  * Permission to use, copy, and distribute for non-commercial purposes,
  39.  * is hereby granted without fee, providing that the above copyright
  40.  * notice appear in all copies and that both the copyright notice and this
  41.  * permission notice appear in supporting documentation.
  42.  *
  43.  * The software may be modified for your own purposes, but modified versions
  44.  * may not be distributed.
  45.  *
  46.  * This software is provided "as is" without any expressed or implied warranty.
  47.  *
  48.  * The author may be contacted via:
  49.  *    US Mail:   John Bradley
  50.  *               GRASP Lab, Room 301C
  51.  *               3401 Walnut St.
  52.  *               Philadelphia, PA  19104
  53.  *
  54.  *    Phone:     (215) 898-8813
  55.  *    EMail:     bradley@cis.upenn.edu
  56.  */
  57.  
  58.  
  59. #include "xv.h"
  60.  
  61. typedef long int        count_int;
  62.  
  63. static int  Width, Height;
  64. static int  curx, cury;
  65. static long CountDown;
  66. static int  Interlace;
  67. static byte bw[2] = {0, 0xff};
  68.  
  69. #ifdef __STDC__
  70. static void putword(int, FILE *);
  71. static void compress(int, FILE *, byte *, int);
  72. static void output(int);
  73. static void cl_block(void);
  74. static void cl_hash(count_int);
  75. static void char_init(void);
  76. static void char_out(int);
  77. static void flush_char(void);
  78. #else
  79. static void putword(), compress(), output(), cl_block(), cl_hash();
  80. static void char_init(), char_out(), flush_char();
  81. #endif
  82.  
  83. static byte pc2nc[256],r1[256],g1[256],b1[256];
  84.  
  85.  
  86. /*************************************************************/
  87. int WriteGIF(fp, pic, w, h, rmap, gmap, bmap, numcols, colorstyle)
  88. FILE *fp;
  89. byte *pic;
  90. int   w,h;
  91. byte *rmap, *gmap, *bmap;
  92. int   numcols, colorstyle;
  93. {
  94.   int RWidth, RHeight;
  95.   int LeftOfs, TopOfs;
  96.   int Resolution, ColorMapSize, InitCodeSize, Background, BitsPerPixel;
  97.   int i,j,nc;
  98.  
  99.  
  100.   /* if writing B/W stipple... */
  101.   if (colorstyle==2) {
  102.     rmap = gmap = bmap = bw;
  103.     numcols = 2;
  104.   }
  105.  
  106.   Interlace = 0;
  107.   Background = 0;
  108.  
  109.  
  110.   for (i=0; i<256; i++) { pc2nc[i] = r1[i] = g1[i] = b1[i] = 0; }
  111.  
  112.   /* compute number of unique colors */
  113.   nc = 0;
  114.  
  115.   for (i=0; i<numcols; i++) {
  116.     /* see if color #i is already used */
  117.     for (j=0; j<i; j++) {
  118.       if (rmap[i] == rmap[j] && gmap[i] == gmap[j] && 
  119.       bmap[i] == bmap[j]) break;
  120.     }
  121.  
  122.     if (j==i) {  /* wasn't found */
  123.       pc2nc[i] = nc;
  124.       r1[nc] = rmap[i];
  125.       g1[nc] = gmap[i];
  126.       b1[nc] = bmap[i];
  127.       nc++;
  128.     }
  129.     else pc2nc[i] = pc2nc[j];
  130.   }
  131.  
  132.  
  133.   /* figure out 'BitsPerPixel' */
  134.   for (i=1; i<8; i++)
  135.     if ( (1<<i) >= nc) break;
  136.   
  137.   BitsPerPixel = i;
  138.  
  139.   ColorMapSize = 1 << BitsPerPixel;
  140.     
  141.   RWidth  = Width  = w;
  142.   RHeight = Height = h;
  143.   LeftOfs = TopOfs = 0;
  144.     
  145.   Resolution = BitsPerPixel;
  146.  
  147.   CountDown = w * h;    /* # of pixels we'll be doing */
  148.  
  149.   if (BitsPerPixel <= 1) InitCodeSize = 2;
  150.                     else InitCodeSize = BitsPerPixel;
  151.  
  152.   curx = cury = 0;
  153.  
  154.   if (!fp) {
  155.     fprintf(stderr,  "WriteGIF: file not open for writing\n" );
  156.     return (1);
  157.   }
  158.  
  159.   if (DEBUG) 
  160.     fprintf(stderr,"WrGIF: pic=%lx, w,h=%dx%d, numcols=%d, Bits%d,Cmap=%d\n",
  161.         pic, w,h,numcols,BitsPerPixel,ColorMapSize);
  162.  
  163.   fwrite("GIF87a", 1, 6, fp);    /* the GIF magic number */
  164.  
  165.   putword(RWidth, fp);           /* screen descriptor */
  166.   putword(RHeight, fp);
  167.  
  168.   i = 0x80;                     /* Yes, there is a color map */
  169.   i |= (8-1)<<4;                 /* OR in the color resolution (hardwired 8) */
  170.   i |= (BitsPerPixel - 1);       /* OR in the # of bits per pixel */
  171.   fputc(i,fp);          
  172.  
  173.   fputc(Background, fp);         /* background color */
  174.  
  175.   fputc(0, fp);                  /* future expansion byte */
  176.  
  177.  
  178.   if (colorstyle == 1) {         /* greyscale */
  179.     for (i=0; i<ColorMapSize; i++) {
  180.       j = MONO(r1[i], g1[i], b1[i]);
  181.       fputc(j, fp);
  182.       fputc(j, fp);
  183.       fputc(j, fp);
  184.     }
  185.   }
  186.   else {
  187.     for (i=0; i<ColorMapSize; i++) {       /* write out Global colormap */
  188.       fputc(r1[i], fp);
  189.       fputc(g1[i], fp);
  190.       fputc(b1[i], fp);
  191.     }
  192.   }
  193.  
  194.   fputc( ',', fp );              /* image separator */
  195.  
  196.   /* Write the Image header */
  197.   putword(LeftOfs, fp);
  198.   putword(TopOfs,  fp);
  199.   putword(Width,   fp);
  200.   putword(Height,  fp);
  201.   if (Interlace) fputc(0x40, fp);   /* Use Global Colormap, maybe Interlace */
  202.             else fputc(0x00, fp);
  203.  
  204.   fputc(InitCodeSize, fp);
  205.   compress(InitCodeSize+1, fp, pic, w*h);
  206.  
  207.   fputc(0,fp);                      /* Write out a Zero-length packet (EOF) */
  208.   fputc(';',fp);                    /* Write GIF file terminator */
  209.  
  210.   return (0);
  211. }
  212.  
  213.  
  214.  
  215.  
  216. /******************************/
  217. static void putword(w, fp)
  218. int w;
  219. FILE *fp;
  220. {
  221.   /* writes a 16-bit integer in GIF order (LSB first) */
  222.   fputc(w & 0xff, fp);
  223.   fputc((w>>8)&0xff, fp);
  224. }
  225.  
  226.  
  227.  
  228.  
  229. /***********************************************************************/
  230.  
  231.  
  232. static unsigned long cur_accum = 0;
  233. static int           cur_bits = 0;
  234.  
  235.  
  236.  
  237.  
  238. #define min(a,b)        ((a>b) ? b : a)
  239.  
  240. #define BITS    12
  241. #define MSDOS    1
  242.  
  243. #define HSIZE  5003            /* 80% occupancy */
  244.  
  245. typedef unsigned char   char_type;
  246.  
  247.  
  248. static int n_bits;                   /* number of bits/code */
  249. static int maxbits = BITS;           /* user settable max # bits/code */
  250. static int maxcode;                  /* maximum code, given n_bits */
  251. static int maxmaxcode = 1 << BITS;   /* NEVER generate this */
  252.  
  253. #define MAXCODE(n_bits)     ( (1 << (n_bits)) - 1)
  254.  
  255. static  count_int      htab [HSIZE];
  256. static  unsigned short codetab [HSIZE];
  257. #define HashTabOf(i)   htab[i]
  258. #define CodeTabOf(i)   codetab[i]
  259.  
  260. static int hsize = HSIZE;            /* for dynamic table sizing */
  261.  
  262. /*
  263.  * To save much memory, we overlay the table used by compress() with those
  264.  * used by decompress().  The tab_prefix table is the same size and type
  265.  * as the codetab.  The tab_suffix table needs 2**BITS characters.  We
  266.  * get this from the beginning of htab.  The output stack uses the rest
  267.  * of htab, and contains characters.  There is plenty of room for any
  268.  * possible stack (stack used to be 8000 characters).
  269.  */
  270.  
  271. #define tab_prefixof(i) CodeTabOf(i)
  272. #define tab_suffixof(i)        ((char_type *)(htab))[i]
  273. #define de_stack               ((char_type *)&tab_suffixof(1<<BITS))
  274.  
  275. static int free_ent = 0;                  /* first unused entry */
  276.  
  277. /*
  278.  * block compression parameters -- after all codes are used up,
  279.  * and compression rate changes, start over.
  280.  */
  281. static int clear_flg = 0;
  282.  
  283. static long int in_count = 1;            /* length of input */
  284. static long int out_count = 0;           /* # of codes output (for debugging) */
  285.  
  286. /*
  287.  * compress stdin to stdout
  288.  *
  289.  * Algorithm:  use open addressing double hashing (no chaining) on the 
  290.  * prefix code / next character combination.  We do a variant of Knuth's
  291.  * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
  292.  * secondary probe.  Here, the modular division first probe is gives way
  293.  * to a faster exclusive-or manipulation.  Also do block compression with
  294.  * an adaptive reset, whereby the code table is cleared when the compression
  295.  * ratio decreases, but after the table fills.  The variable-length output
  296.  * codes are re-sized at this point, and a special CLEAR code is generated
  297.  * for the decompressor.  Late addition:  construct the table according to
  298.  * file size for noticeable speed improvement on small files.  Please direct
  299.  * questions about this implementation to ames!jaw.
  300.  */
  301.  
  302. static int g_init_bits;
  303. static FILE *g_outfile;
  304.  
  305. static int ClearCode;
  306. static int EOFCode;
  307.  
  308.  
  309. /********************************************************/
  310. static void compress(init_bits, outfile, data, len)
  311. int   init_bits;
  312. FILE *outfile;
  313. byte *data;
  314. int   len;
  315. {
  316.   register long fcode;
  317.   register int i = 0;
  318.   register int c;
  319.   register int ent;
  320.   register int disp;
  321.   register int hsize_reg;
  322.   register int hshift;
  323.  
  324.   /*
  325.    * Set up the globals:  g_init_bits - initial number of bits
  326.    *                      g_outfile   - pointer to output file
  327.    */
  328.   g_init_bits = init_bits;
  329.   g_outfile   = outfile;
  330.  
  331.   /* initialize 'compress' globals */
  332.   maxbits = BITS;
  333.   maxmaxcode = 1<<BITS;
  334.   memset((char *) htab, 0, sizeof(htab));
  335.   memset((char *) codetab, 0, sizeof(codetab));
  336.   hsize = HSIZE;
  337.   free_ent = 0;
  338.   clear_flg = 0;
  339.   in_count = 1;
  340.   out_count = 0;
  341.   cur_accum = 0;
  342.   cur_bits = 0;
  343.  
  344.  
  345.   /*
  346.    * Set up the necessary values
  347.    */
  348.   out_count = 0;
  349.   clear_flg = 0;
  350.   in_count = 1;
  351.   maxcode = MAXCODE(n_bits = g_init_bits);
  352.  
  353.   ClearCode = (1 << (init_bits - 1));
  354.   EOFCode = ClearCode + 1;
  355.   free_ent = ClearCode + 2;
  356.  
  357.   char_init();
  358.   ent = pc2nc[*data++];  len--;
  359.  
  360.   hshift = 0;
  361.   for ( fcode = (long) hsize;  fcode < 65536L; fcode *= 2L )
  362.     hshift++;
  363.   hshift = 8 - hshift;                /* set hash code range bound */
  364.  
  365.   hsize_reg = hsize;
  366.   cl_hash( (count_int) hsize_reg);            /* clear hash table */
  367.  
  368.   output(ClearCode);
  369.     
  370.   while (len) {
  371.     c = pc2nc[*data++];  len--;
  372.     in_count++;
  373.  
  374.     fcode = (long) ( ( (long) c << maxbits) + ent);
  375.     i = (((int) c << hshift) ^ ent);    /* xor hashing */
  376.  
  377.     if ( HashTabOf (i) == fcode ) {
  378.       ent = CodeTabOf (i);
  379.       continue;
  380.     }
  381.  
  382.     else if ( (long)HashTabOf (i) < 0 )      /* empty slot */
  383.       goto nomatch;
  384.  
  385.     disp = hsize_reg - i;           /* secondary hash (after G. Knott) */
  386.     if ( i == 0 )
  387.       disp = 1;
  388.  
  389. probe:
  390.     if ( (i -= disp) < 0 )
  391.       i += hsize_reg;
  392.  
  393.     if ( HashTabOf (i) == fcode ) {
  394.       ent = CodeTabOf (i);
  395.       continue;
  396.     }
  397.  
  398.     if ( (long)HashTabOf (i) > 0 ) 
  399.       goto probe;
  400.  
  401. nomatch:
  402.     output(ent);
  403.     out_count++;
  404.     ent = c;
  405.  
  406.     if ( free_ent < maxmaxcode ) {
  407.       CodeTabOf (i) = free_ent++; /* code -> hashtable */
  408.       HashTabOf (i) = fcode;
  409.     }
  410.     else
  411.       cl_block();
  412.   }
  413.  
  414.   /* Put out the final code */
  415.   output(ent);
  416.   out_count++;
  417.   output(EOFCode);
  418. }
  419.  
  420.  
  421. /*****************************************************************
  422.  * TAG( output )
  423.  *
  424.  * Output the given code.
  425.  * Inputs:
  426.  *      code:   A n_bits-bit integer.  If == -1, then EOF.  This assumes
  427.  *              that n_bits =< (long)wordsize - 1.
  428.  * Outputs:
  429.  *      Outputs code to the file.
  430.  * Assumptions:
  431.  *      Chars are 8 bits long.
  432.  * Algorithm:
  433.  *      Maintain a BITS character long buffer (so that 8 codes will
  434.  * fit in it exactly).  Use the VAX insv instruction to insert each
  435.  * code in turn.  When the buffer fills up empty it and start over.
  436.  */
  437.  
  438. static
  439. unsigned long masks[] = { 0x0000, 0x0001, 0x0003, 0x0007, 0x000F,
  440.                                   0x001F, 0x003F, 0x007F, 0x00FF,
  441.                                   0x01FF, 0x03FF, 0x07FF, 0x0FFF,
  442.                                   0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF };
  443.  
  444. static void output(code)
  445. int code;
  446. {
  447.   cur_accum &= masks[cur_bits];
  448.  
  449.   if (cur_bits > 0)
  450.     cur_accum |= ((long)code << cur_bits);
  451.   else
  452.     cur_accum = code;
  453.     
  454.   cur_bits += n_bits;
  455.  
  456.   while( cur_bits >= 8 ) {
  457.     char_out( (unsigned int) (cur_accum & 0xff) );
  458.     cur_accum >>= 8;
  459.     cur_bits -= 8;
  460.   }
  461.  
  462.   /*
  463.    * If the next entry is going to be too big for the code size,
  464.    * then increase it, if possible.
  465.    */
  466.  
  467.   if (free_ent > maxcode || clear_flg) {
  468.  
  469.     if( clear_flg ) {
  470.       maxcode = MAXCODE (n_bits = g_init_bits);
  471.       clear_flg = 0;
  472.     }
  473.     else {
  474.       n_bits++;
  475.       if ( n_bits == maxbits )
  476.     maxcode = maxmaxcode;
  477.       else
  478.     maxcode = MAXCODE(n_bits);
  479.     }
  480.   }
  481.     
  482.   if( code == EOFCode ) {
  483.     /* At EOF, write the rest of the buffer */
  484.     while( cur_bits > 0 ) {
  485.       char_out( (unsigned int)(cur_accum & 0xff) );
  486.       cur_accum >>= 8;
  487.       cur_bits -= 8;
  488.     }
  489.  
  490.     flush_char();
  491.     
  492.     fflush( g_outfile );
  493.  
  494.     if( ferror( g_outfile ) )
  495.       FatalError("unable to write GIF file");
  496.   }
  497. }
  498.  
  499.  
  500. /********************************/
  501. static void cl_block ()             /* table clear for block compress */
  502. {
  503.   /* Clear out the hash table */
  504.  
  505.   cl_hash ( (count_int) hsize );
  506.   free_ent = ClearCode + 2;
  507.   clear_flg = 1;
  508.  
  509.   output(ClearCode);
  510. }
  511.  
  512.  
  513. /********************************/
  514. static void cl_hash(hsize)          /* reset code table */
  515. register count_int hsize;
  516. {
  517.   register count_int *htab_p = htab+hsize;
  518.   register long i;
  519.   register long m1 = -1;
  520.  
  521.   i = hsize - 16;
  522.   do {                            /* might use Sys V memset(3) here */
  523.     *(htab_p-16) = m1;
  524.     *(htab_p-15) = m1;
  525.     *(htab_p-14) = m1;
  526.     *(htab_p-13) = m1;
  527.     *(htab_p-12) = m1;
  528.     *(htab_p-11) = m1;
  529.     *(htab_p-10) = m1;
  530.     *(htab_p-9) = m1;
  531.     *(htab_p-8) = m1;
  532.     *(htab_p-7) = m1;
  533.     *(htab_p-6) = m1;
  534.     *(htab_p-5) = m1;
  535.     *(htab_p-4) = m1;
  536.     *(htab_p-3) = m1;
  537.     *(htab_p-2) = m1;
  538.     *(htab_p-1) = m1;
  539.     htab_p -= 16;
  540.   } while ((i -= 16) >= 0);
  541.  
  542.   for ( i += 16; i > 0; i-- )
  543.     *--htab_p = m1;
  544. }
  545.  
  546.  
  547. /******************************************************************************
  548.  *
  549.  * GIF Specific routines
  550.  *
  551.  ******************************************************************************/
  552.  
  553. /*
  554.  * Number of characters so far in this 'packet'
  555.  */
  556. static int a_count;
  557.  
  558. /*
  559.  * Set up the 'byte output' routine
  560.  */
  561. static void char_init()
  562. {
  563.     a_count = 0;
  564. }
  565.  
  566. /*
  567.  * Define the storage for the packet accumulator
  568.  */
  569. static char accum[ 256 ];
  570.  
  571. /*
  572.  * Add a character to the end of the current packet, and if it is 254
  573.  * characters, flush the packet to disk.
  574.  */
  575. static void char_out(c)
  576. int c;
  577. {
  578.   accum[ a_count++ ] = c;
  579.   if( a_count >= 254 ) 
  580.     flush_char();
  581. }
  582.  
  583. /*
  584.  * Flush the packet to disk, and reset the accumulator
  585.  */
  586. static void flush_char()
  587. {
  588.   if( a_count > 0 ) {
  589.     fputc( a_count, g_outfile );
  590.     fwrite( accum, 1, a_count, g_outfile );
  591.     a_count = 0;
  592.   }
  593. }    
  594.